package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no32;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestValidParentheses(")(()()()))()"));
    }

    /**
     * 正确解法 动态规划 O(n)
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        int max = 0;
        int sl = s.length();
        int[] dp = new int[sl];
        for(int i = 1;i < sl;i ++){
            if(s.charAt(i) == ')'){
                // 如果前一个字符时和当前连续， 则为前一个字符前的长度 + 2
                if(s.charAt(i - 1) == '('){
                    dp[i] =  (i >= 2 ? (dp[i - 2]) : 0 ) + 2;
                }
                else {
                    // 减去前一个字符最大连续长度后剩余的长度 如果有剩余
                    // 判断剩余的最后一位能否与当前连续
                    int temp = i - dp[i - 1];
                    if(temp > 0 && s.charAt(temp - 1) == '('){
                        //能连续的情况， 则为前一个 + 前一个再往前的 + 2
                        dp[i] = dp[i - 1] + (temp >= 2 ? dp[temp - 2] : 0) + 2;
                    }
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }

    //超出时间限制。。 动态规划
    // n * (n - 1) / 2
    public int longestValidParentheses2(String s) {
        int sl = s.length();
        Info[] last = null;
        Info[] cur = null;
        int max = 0;
        for (int i = sl - 1; i >= 0; i--) {
            cur = new Info[sl - i];
            int curIndex = sl - i - 1;
            cur[curIndex] = new Info();
            if (s.charAt(i) == ')') {
                cur[curIndex].sNum += 1;
            }
            for (int j = i + 1; j < sl; j++) {
                int index = sl - j - 1 ;
                if (cur[curIndex].sNum == 1) {
                    cur[index] = new Info(last[index]);
                    cur[index].sNum += 1;
                } else {
                    if (last[index].pNum < last[index].sNum) {
                        cur[index] = new Info(last[index]);
                        cur[index].pNum += 1;
                        if (cur[index].sNum == cur[index].pNum) {
                            max = Math.max(cur[index].sNum, max);
                        }
                    } else {
                        cur[index] = new Info();
                    }
                }
            }
            last = cur;
        }

        return max * 2;
    }

    class Info {
        int sNum;
        int pNum;

        public Info() {

        }

        public Info(Info info) {
            this.sNum = info.sNum;
            this.pNum = info.pNum;
        }
    }
}
